#include <bits/stdc++.h>

using namespace std;

class Solution
{
public:
    // bool isValid(string s)
    // {
    //     stack<char> stk;
    //     int length = s.size();
    //     for (int i = 0; i < length; i++)
    //     {
    //         if (i == 0 && (s[i] == '(' || s[i] == '{' || s[i] == '['))
    //         {
    //             stk.push(s[i]);
    //             continue;
    //         }
    //         else if (i == 0 && (s[i] == ')' || s[i] == '}' || s[i] == ']'))
    //         {
    //             return false;
    //         }
    //         if (s[i] == '(' || s[i] == '[' || s[i] == '{')
    //         {
    //             stk.push(s[i]);
    //         }
    //         else if (stk.size() == 0)
    //         {
    //             return false;
    //         }
    //         else if ((stk.top() == '(' && s[i] == ')') || (stk.top() == '[' && s[i] == ']') || (stk.top() == '{' && s[i] == '}'))
    //         {
    //             stk.pop();
    //         }
    //         else
    //         {
    //             return false;
    //         }
    //     }
    //     if (stk.empty())
    //     {
    //         return true;
    //     }
    //     else
    //     {
    //         return false;
    //     }
    // }

    bool isValid(string s)
    {
        int length = s.size();
        if (length % 2 != 0)
        {
            return false;
        }
        stack<char> stk;
        for (int i = 0; i < length; i++)
        {
            if (s[i] == '(')
                stk.push(')');
            else if (s[i] == '[')
                stk.push(']');
            else if (s[i] == '{')
                stk.push('}');
            else if (stk.empty() || s[i] != stk.top())
                return false;
            else
                stk.pop();
        }
        return stk.empty();
    }
};

int main()
{
    string s = "()[]{}";
    Solution sol;
    cout << sol.isValid(s) << endl;
    return 0;
}